import java.util.LinkedList;

public class SearchStrategy
{
	 int DFCounter =0;
	String	typeOfSearch;
	int i =0;
	public SearchStrategy(String typeOfSearch)
	{
		super();
		this.typeOfSearch = typeOfSearch;
	}

	public String getTypeOfSearch()
	{
		return typeOfSearch;
	}

	public void setTypeOfSearch(String typeOfSearch)
	{
		this.typeOfSearch = typeOfSearch;
	}

	public LinkedList<Node> search(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{

		if (getTypeOfSearch().equals("BF"))
		{
			visitedNodes = BFSearch(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("DF"))
		{
			visitedNodes = DFSearch(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("ID"))
		{
			visitedNodes = DFIterativeSearch(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("GR1"))
		{
			visitedNodes = GR1Search(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("GR2"))
		{
			visitedNodes = GR2Search(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("AS1"))
		{
			visitedNodes = AS1Search(visitedNodes, exploredNode);
		}
		if (getTypeOfSearch().equals("AS2"))
		{
			visitedNodes = AS2Search(visitedNodes, exploredNode);
		}
		return visitedNodes;
	}

	public LinkedList<Node> BFSearch(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		while (!nodeChildren.isEmpty())
		{
			visitedNodes.addLast(nodeChildren.pop());
		}
		return visitedNodes;
	}

	public LinkedList<Node> DFSearch(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{

		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		while (!nodeChildren.isEmpty())
		{
			visitedNodes.addFirst(nodeChildren.pop());
		}
		return visitedNodes;
	}

	public LinkedList<Node> DFIterativeSearch(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		
		LinkedList<Node> r =  new LinkedList<Node>();
		if(exploredNode.getBlocktoBeMoved() != null&&exploredNode.isGoal(exploredNode)) 
			{
				r.add(exploredNode); return r ;
			}
			
		
		if(i<=DFCounter)
		{
			LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);
			i++;
			
			
			while (!nodeChildren.isEmpty())
			{
				visitedNodes.addFirst(nodeChildren.pop());
			}
			
		}
		if(visitedNodes.isEmpty()) return r;	
			
			return DFIterativeSearch(visitedNodes, visitedNodes.pop());
		
		
	}

	public LinkedList<Node> GR1Search(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		// assign scores to nodes
		int sizeOfChildren = nodeChildren.size();
		for (int i = 0; i < sizeOfChildren; i++)
		{
			Board b = nodeChildren.get(i).getCurrentState().getCurrentBoard();
			int mouseLocation = b.getMouseLocation(b);
			int score = b.h1(mouseLocation);
			nodeChildren.get(i).setScore(score);
		}
		while (!nodeChildren.isEmpty())
		{
			visitedNodes.add(nodeChildren.pop());
		}
		// sort queue according to score
		srtByScore(visitedNodes);
		return visitedNodes;
	}

	public LinkedList<Node> GR2Search(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		// assign scores to nodes
		int sizeOfChildren = nodeChildren.size();
		for (int i = 0; i < sizeOfChildren; i++)
		{
			Board b = nodeChildren.get(i).getCurrentState().getCurrentBoard();
			int mouseLocation = b.getMouseLocation(b);
			int score = b.h2(mouseLocation, b);
			nodeChildren.get(i).setScore(score);
		}
		while (!nodeChildren.isEmpty())
		{
			visitedNodes.add(nodeChildren.pop());
		}
		// sort queue according to score
		srtByScore(visitedNodes);
		return visitedNodes;
	}

	public LinkedList<Node> AS1Search(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		// assign scores to nodes
		int sizeOfChildren = nodeChildren.size();
		for (int i = 0; i < sizeOfChildren; i++)
		{
			Board b = nodeChildren.get(i).getCurrentState().getCurrentBoard();
			int mouseLocation = b.getMouseLocation(b);
			int heuristicScore = b.h1(mouseLocation);
			int pathCost = nodeChildren.get(i).getLevel();
			int score = heuristicScore + pathCost;
			nodeChildren.get(i).setScore(score);
		}
		while (!nodeChildren.isEmpty())
		{
			visitedNodes.add(nodeChildren.pop());
		}
		// sort queue according to score
		srtByScore(visitedNodes);
		return visitedNodes;
	}

	public LinkedList<Node> AS2Search(LinkedList<Node> visitedNodes,
			Node exploredNode)
	{
		LinkedList<Node> nodeChildren = exploredNode.insertInList(exploredNode);

		// assign scores to nodes
		int sizeOfChildren = nodeChildren.size();
		for (int i = 0; i < sizeOfChildren; i++)
		{
			Board b = nodeChildren.get(i).getCurrentState().getCurrentBoard();
			int mouseLocation = b.getMouseLocation(b);
			int heuristicScore = b.h2(mouseLocation, b);
			int pathCost = nodeChildren.get(i).getLevel();
			int score = heuristicScore + pathCost;
			nodeChildren.get(i).setScore(score);
		}
		while (!nodeChildren.isEmpty())
		{
			visitedNodes.add(nodeChildren.pop());
		}
		// sort queue according to score
		srtByScore(visitedNodes);
		return visitedNodes;
	}

	public static void srtByScore(LinkedList<Node> nodes)
	{

		int n = nodes.size();
		do
		{
			int newN = 0;
			for (int i = 1; i < nodes.size() - 1; i++)
			{
				if (nodes.get(i - 1).getScore() > nodes.get(i).getScore())
				{
					// swapping the nodes in the list
					Node tempNode1 = nodes.get(i);
					Node tempNode2 = nodes.get(i - 1);
					nodes.set(i - 1, tempNode1);
					nodes.set(i, tempNode2);
					newN = i;
				}
			}
			n = newN;

		} while (n != 0);
	}

	public  int getDFCounter() {
		return DFCounter;
	}

	public  void setDFCounter(int dFCounter) {
		DFCounter = dFCounter;
	}

	public int getI() {
		return i;
	}

	public void setI(int i) {
		this.i = i;
	}
}